package q522_findLUSlength;

import java.util.Arrays;
import java.util.Comparator;

public class Solution {
    /*
    实际上就是找最长的孤儿字符串 这个字符串不能是其他字符串的子串而已
    首先按照字符串长度排序 这样只要找到第一个就可以直接返回
     */
    public int findLUSlength(String[] strs) {
        Arrays.sort(strs, new Comparator<String>(){
            @Override
            public int compare(String s1, String s2){
                return s2.length() - s1.length();
            }
        });

        boolean find = false;
        int maxLen = strs[0].length();
        for (int i = 0; i < strs.length; i++) {
            maxLen = strs[i].length();
            boolean LUS = true;
            for (int j = 0; j < strs.length; j++) {
                if (i == j) continue;
                if (strs[j].length() < maxLen) break;
                if(judge(strs[i], strs[j])){
                    LUS = false;
                    break;
                }
            }
            if (LUS) {
                find = true;
                break;
            }
        }

        return find ? maxLen : -1;
    }

    /*
    判断s1是否为s2的子串
     */
    private boolean judge(String s1, String s2){
        if (s1.length() == s2.length()) return s1.equals(s2);
        int i = 0, j = 0;
        while (i < s1.length() && j < s2.length()) {
            if (s1.charAt(i) == s2.charAt(j)) i++;
            j++;
        }

        return i == s1.length();
    }
}
